package org.datastructure.secondday.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{53, 3, 542, 748, 14, 214};
        radixSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    public static void radixSort(int... arr) {

        // TODO: step1创建桶，和标识桶中是否有元素的数组
        int[][] buckets = new int[10][arr.length];
        int[] bucketElementCounts = new int[10];

        // TODO: step 1 先将数组根据不同位上的数依次放入木桶中去
        // TODO: 根据最大数的位数决定排序次数,要算出每次从个位数/十位/百位。。。进行排序，必须要先除以1/10/100
        int length = (Arrays.stream(arr).max().getAsInt() + "").length();
        int digitOfBucket = 0;
        int index = 0;
        for (int l = 0, n = 1; l < length; l++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                digitOfBucket = arr[i] / n % 10;
                // TODO:  bucketElementCounts[digitOfBucket]=buckets这个二维数组列数
                buckets[digitOfBucket][bucketElementCounts[digitOfBucket]++] = arr[i];
            }
            // TODO: step 2 将桶中的元素按照桶的顺序，和桶中从小到大依次放入原数组
            index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int j = 0; j < bucketElementCounts[k]; j++) {
                        // TODO: 存的时候bucketElementCounts[digitOfBucket]和buckets的行下标是对应的，
                        //   即bucketElementCounts[digitOfBucket]中存的是buckets行中的元素个数
                        arr[index++] = buckets[k][j];
                    }
                }
                // TODO: 这里要将元素个数清空，否则下次将桶中数据赋值给arr使，致使判断错误和取数据错误
                bucketElementCounts[k] = 0;
            }
        }
    }
}
